#include <iostream>
#include <vector>
#include <cstdio> 
#include <cstring>
#include <queue>

#define in read()
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef double db;
typedef vector < int >  vec;
typedef pair < int , int > pii;

int read() {
  int x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch == '-',ch = getchar();
  while(isdigit(ch)) x = x * 10 + (ch ^ 48),ch = getchar(); return f ? -x : x;
}

const int N = 110;
const int S = 1025;
const int inf = 0x3f3f3f3f;

int f[N][S],n,m,K;
bool vis[N];
vector < pii > G[N];
priority_queue < pii , vector < pii > , greater < pii > > q;

void dijk(int s) {
    memset(vis,0,sizeof vis);
    while(!q.empty()) {
	int x = q.top().se; q.pop(); if(vis[x]) continue; vis[x] = 1;
	for(auto d : G[x])
	    if(f[d.fi][s] > f[x][s] + d.se) f[d.fi][s] = f[x][s] + d.se,q.push({f[d.fi][s],d.fi});
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    n = in,m = in,K = in; for(int i = 1,u,v,w;i <= m;i++) u = in,v = in,w = in,G[u].pb({v,w}),G[v].pb({u,w});
    memset(f,0x3f,sizeof f); for(int i = 0;i < K;i++) f[in][1 << i] = 0;
    for(int s = 1;s < 1 << K;s++) {
	for(int ns = s;ns;ns = (ns - 1) & s) 
	    for(int i = 1;i <= n;i++)
		f[i][s] = min(f[i][s],f[i][ns]+f[i][ns ^ s]);
	for(int i = 1;i <= n;i++) if(f[i][s] < inf) q.push({f[i][s],i});
	dijk(s);
    }
    int ans = inf; for(int i = 1;i <= n;i++) ans = min(ans,f[i][(1 << K) - 1]);
    printf("%d\n",ans); return 0;
} 
